#include <iostream>
using namespace std;

struct Node {
  int val;
  Node *next;
};

Node *PartList(Node *Head, int K) {
  if (Head == nullptr) {
    return Head;
  }
  Node *SmallHead = nullptr, *SmallTail = nullptr;
  Node *EqHead = nullptr, *EqTail = nullptr;
  Node *BigHead = nullptr, *BigTail = nullptr;

  Node *pNow = Head;
  Node *pNext = Head->next;
  while (pNow != nullptr) {
    Node *PtempHead = nullptr;
    Node *PtempTail = nullptr;

    if (pNow->val < K) {
      PtempHead = SmallHead;
      PtempTail = SmallTail;
    } else if (pNow->val == K) {
      PtempHead = EqHead;
      PtempTail = EqTail;
    } else {
      PtempHead = BigHead;
      PtempTail = BigTail;
    }

    if (PtempHead == nullptr) {
      PtempHead = pNow;
    } else {
      PtempTail->next = pNow;
    }
    PtempTail = pNow;
    PtempTail->next = nullptr;
    pNow = pNext;
    pNext = pNow->next;
  }

  if (SmallTail != nullptr) {
    SmallTail->next = (EqHead == nullptr)?(BigHead):(EqHead);
  }
  if (EqTail != nullptr) {
    EqTail->next = BigHead;
  }
  return (SmallHead == nullptr) ? ((EqHead == nullptr) ? (BigHead) : (EqHead))
                                : (SmallHead);
}

int main(int argc, char *argv[]) { return 0; }
